|
|
Optimalizace agentního kódu
Hemala, Luboš ; Kočí, Radek (oponent) ; Zbořil, František (vedoucí práce)
Tato práce navazuje na předchozí snahu o vylepšování překladače agentního jazyka AHLL. Integrované optimalizace se zaměřují především na snížení velikosti cílového kódu v ALLL, proto je v této verzi rozšířena implementace o alokaci registrů barvením grafů. Prezentovány jsou také změny jazyka AHLL, které ovšem vyžadují složitější strukturu překladače. Celkové dosažené výsledky nového překladače potom vykazují průměrně o 35 % menší velikost výsledného kódu pro vyhodnocované komplexní agenty.
|
|
|
Barvení grafů
Procházka, Lukáš ; Goldefus, Filip (oponent) ; Masopust, Tomáš (vedoucí práce)
Tato práce se zabývá barvením grafů, což je přiřazování barev jednotlivým vrcholům grafu tak, aby žádné dva vrcholy spojené hranou neměly stejnou barvu. Tento problém je velmi výpočetně náročný, protože je NP-úplný. Zároveň je velmi důležitý, protože má řadu praktických aplikací. Zde jsou popsány některé heuristické algoritmy, které se tento problém snaží řešit pomocí postupného zlepšování počátečního řešení při zadaném počtu barev. Tři algoritmy byly implementovány a poté otestovány na různých grafech a porovnány vzhledem k různým kritériím.
|
|
|
Metody pro obarvení uzlů multigrafu
Knotek, Martin ; Kunovský, Jiří (oponent) ; Šátek, Václav (vedoucí práce)
Tato práce se zabývá algoritmy pro vrcholové barvení a jejich aplikaci na barvení prvků elektrické rozvodné sítě nízkého napětí. Výsledkem práce je program zobrazující průběh barvení pěti implementovaných metod na zvoleném grafu, který představuje distribuční síť elektrické energie ve městě.
|
|
|
Teorie a aplikace metod Monte Carlo
Hruda, Petr ; Šimek, Václav (oponent) ; Bidlo, Michal (vedoucí práce)
Tato bakalářská práce pojednává o aplikacích metod Monte Carlo na různé problémy. Konkrétně byly užity algoritmy Metropolis a Simulované žíhání na optimalizaci problému obchodního cestujícího a problému barvení grafů. Navíc bylo využito základního přístupu Monte Carla pro statistické analyzování elektronických obvodů, ve kterých různé komponenty vykazují náhodné odchylky v dané toleranci. Výsledky jsou vyhodnoceny pro různé konfigurace parametrů Monte Carlo metod.
|
|
|
Optimalizace dopravně-inženýrských úloh
Le, Huy ; Hošek, Jaromír (oponent) ; Hrabec, Dušan (vedoucí práce)
Tato bakalářská práce se zabývá optimalizací řízení světelných signalizačních zařízení křižovatky, přesněji hledá optimální minimální signální plán příslušné křižovatky za splnění daných předpokladů a požadavků. Teoretická část se zaměřuje na uvedení předpokladů a základních pojmů, dále také podrobněji charakterizuje úlohu a popisuje použitelné algoritmy na tuto úlohu. Praktická část se věnuje aplikací těchto algoritmů na specifickém příkladu křižovatky a následně získané výsledky srovnává.
|
|
|
Informační systém pro školy s automatickou tvorbou rozvrhů
Švadlenka, Jiří ; Jurka, Pavel (oponent) ; Chmelař, Petr (vedoucí práce)
Tato práce se věnuje použitím informačního systému pro správu školní agendy. Školy jsou nuceny spravovat velké množství informací a to nejenom o svých studentech. Samotná problematika je velmi rozsáhlá a různorodá. Proto jsou uvedeny nejběžnější typy dat a požadavků škol na provoz školního informačního systému. Součástí školního informačního systému je systém pro automatické generování rozvrhů. Nejdříve jsou definovány základní pojmy z oblasti rozvrhování, na které navazují metody a algoritmy pro řešení problému vytvoření školních rozvrhů. Školní rozvrhování je problém naplánování výuky, za určitých omezujících podmínek. Dále se práce věnuje návrhu školního informačního systému, organizování dat v nich a řešením problémů při jeho návrhu. Navrhovaný informační systém klade důraz na jednoduchou rozšiřitelnost a širokou možnost využití. V této části práce je také uveden navrhovaný algoritmus pro řešení definovaného školního rozvrhování.
|
|
|
Barvení grafu, klika v grafu, algoritmy a aplikace
Valachová, Alžbeta ; Dvořák, Jiří (oponent) ; Šeda, Miloš (vedoucí práce)
Táto diplomová práca sa zaoberá problematikou farbenia grafu a hľadaním kliky v grafe, s dôrazom na popis algoritmov a ich aplikácie. Farbenie grafu je proces priraďovania farieb jednotlivým vrcholom grafu tak, aby susedné vrcholy mali odlišné farby. Táto problematika je dôležitá pre riešenie rôznych optimalizačných úloh. Práca sa zameriava aj na hľadanie kliky v grafe, čo je dôležitý problém v analýze sociálnych sietí alebo rozpoznávaní obrazov. Cieľom práce je poskytnúť komplexný prehľad o~farbení grafu, hľadaní kliky v grafe, predstaviť a analyzovať existujúce algoritmy a ukázať ich aplikácie v praxi.
|
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (vedoucí práce) ; Růžička, Pavel (oponent)
Nechť A je konečná relační struktura. Problém splňování omezení s šablonou A, CSP (a), rozhoduje, zda vstupní struktura X je homomorfní A. Hypotéza o dichotomii CSP Federa a Vardiho říká, že CSP(A) je vždy buď v P nebo NP-úplný. V první části předsdtavíme algebraický přístup k CSP a shrneme známé výsledky o CSP pro orientované grafy, tzv. H-barvení. Ve druhé části se zabýváme jistou třídou orientovaných stromů, tzv. speciálními polyádami. Pomocí algebraického přístupu potvrdíme dichotomickou hypotézu pro speciální polyády. V polynomiálním případě poskytneme jemnější popis a zkontruujeme speciální polyádu T takovou, že CSP(T) je v P, ale T nemá šířku 1 ani žádné near-unanimity polymorfismy.
|
|
|
Variants of graph labeling problems
Masařík, Tomáš ; Fiala, Jiří (vedoucí práce) ; Fellows, Michael R. (oponent) ; Hell, Pavol (oponent)
Tato práce se skládá ze tří částí zasvědcených značkování grafů, dědičným grafovým třídám a parametrizované složitosti. Pakovací barvení, původně označované vysílací barevnost, přiřazuje vrcholům grafu přirozená čísla tak, že vrcholy se stejným číslem musí být od sebe vzdáleny alespoň o hodnotu danného čísla. Tento problém je motivován přiřazováním frekvencí vysílačům. My zlepšujeme těžkost na chordálních grafech. Dokazujeme, že pakovací barvení na chordálních grafech diametru 3 je velice těžké aproximovat. Navíc uvádíme několik pozitivních výsledků pro intervalové grafy a pro související strukturální grafové parametry. Dědičné grafové třídy jsou zachovány při mazání vrcholů. My studujeme grafy takové, které neobsahují podgraf H jako svůj indukovaný podgraf. Dokazujeme, že 3 barvení je polynomiálně řešitelné pro (P3 + P4)-free a (P2 + P5)-free grafy, a tudíž jsme vyřešili poslední otevřené případy pro H-free grafy, kde H má nanejvýš 7 vrcholů. Férové problémy jsou takové modifikace grafových mazacích problémů, kde místo minimalizace velikosti řešení, je cílem minimalizovat maximální počet sousedů ve smazané množině. My ukazujeme, že takové problémy jdou vyřešit ve FPT čase pro MSO1 formuli parametrizováno velikostí formule a twin pokrytím grafu. Navíc definujeme základní férový problém, férové...
|
|
|
Optimalizace dopravně-inženýrských úloh
Le, Huy ; Hošek, Jaromír (oponent) ; Hrabec, Dušan (vedoucí práce)
Tato bakalářská práce se zabývá optimalizací řízení světelných signalizačních zařízení křižovatky, přesněji hledá optimální minimální signální plán příslušné křižovatky za splnění daných předpokladů a požadavků. Teoretická část se zaměřuje na uvedení předpokladů a základních pojmů, dále také podrobněji charakterizuje úlohu a popisuje použitelné algoritmy na tuto úlohu. Praktická část se věnuje aplikací těchto algoritmů na specifickém příkladu křižovatky a následně získané výsledky srovnává.
|
host ::
RSS.